How does Genetic Algorithm Work?

Genetic algorithms work by initially creating a set of random solutions known as the population. At each step of the optimization, the cost function for the entire population is calculated to get a ranked list of solutions.

Once the solutions are ranked, a new population known as the next generation is created.

First, the top solutions in the current population are added to the new population as they are. This process is called elitism. The rest of the new population consists of completely new solutions that are created by modifying the best solutions.

The solutions can be modified in two ways:

Mutation: This is a small, simple, random change to an existing solution. In this case, a mutation can be done simply by picking one of the numbers in the solution and increasing or decreasing it.
Crossover or breeding: The other way to modify solutions is called crossover or breeding. This method involves taking two of the best solutions and combining them in some way. In this case, a simple way to do crossover is to take a random number of elements from one solution and the rest of the elements from another solution.

A new population, usually the same size as the old one, is created by randomly mutating and breeding the best solutions. Then the process repeats; the new population is ranked and another population is created. This continues either for a fixed number of iterations or until there has been no improvement over several generations.

Advantages

Disadvantages

Main Function:



In [ ]:

Example Problems:



In [14]:

    
import time
import random
import math
import optimization

people = [('Seymour','BOS'),
          ('Franny','DAL'),
          ('Zooey','CAK'),
          ('Walt','MIA'),
          ('Buddy','ORD'),
          ('Les','OMA')]
     # LaGuardia airport in New York
destination='LGA'


"""Load this data into a dictionary with the origin and destination (dest) as the keys 
and a list of potential flight details as the values."""
flights={}
     #
for line in file('schedule.txt'):
     origin,dest,depart,arrive,price=line.strip( ).split(',') 
     flights.setdefault((origin,dest),[])
     # Add details to the list of possible flights
     flights[(origin,dest)].append((depart,arrive,int(price)))     

s=[1,4,3,2,7,3,6,3,2,4,5,3] 
domain=[(0,8)]*(len(people)*2)


s=optimization.geneticoptimize(domain,optimization.schedulecost)

optimization.printschedule(s)









    



4559
4277
3901
3883
3772
3564
3564






    



---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-14-a480208d3035> in <module>()
     28 
     29 
---> 30 s=optimization.geneticoptimize(domain,optimization.schedulecost)
     31 
     32 optimization.printschedule(s)

C:\dev\workspace\mygithub\Data_Science\Optimization_Algorithms\optimization.py in geneticoptimize(domain, costf, popsize, step, mutprob, elite, maxiter)
     86   # Main loop
     87   for i in range(maxiter):
---> 88     scores=[(costf(v),v) for v in pop]
     89     scores.sort(  )
     90     ranked=[v for (s,v) in scores]

C:\dev\workspace\mygithub\Data_Science\Optimization_Algorithms\optimization.py in schedulecost(sol)

TypeError: object of type 'NoneType' has no len()



In [ ]:



In [ ]:



In [ ]: